//
//  SplitArray.swift
//  LeetCodeSummary
//
//  Created by WangYonghe on 2020/7/25.
//  Copyright © 2020 WangYonghe. All rights reserved.
//  410. 分割数组的最大值

import UIKit

/*
 410. 分割数组的最大值
 给定一个非负整数数组和一个整数 m，你需要将这个数组分成 m 个非空的连续子数组。设计一个算法使得这 m 个子数组各自和的最大值最小。

 注意:
 数组长度 n 满足以下条件:

 1 ≤ n ≤ 1000
 1 ≤ m ≤ min(50, n)
 示例:

 输入:
 nums = [7,2,5,10,8]
 m = 2

 输出:
 18

 解释:
 一共有四种方法将nums分割为2个子数组。
 其中最好的方式是将其分为[7,2,5] 和 [10,8]，
 因为此时这两个子数组各自的和的最大值为18，在所有情况中最小。
 */

class SplitArray: NSObject {
    
    /*
     动态规划解法：
     「将数组分割为 m 段，求…」是动态规划题目常见的问法
     
     设f[i][j]表示将 i 个数分割成 j 段所能得到的最大连续数组和的最小值。
     
     先考虑 j 的范围。
     我们可以枚举 k ，其中前 k 个数被分割成 j-1 段，后面 k+1 到第 i 个数为第 j 段。
     此时，这 j 段子数组中的和的最大值就是 f[k][j-1] 与 sub(k+1,i)中比较大的值。sub(i,j)表示数组nums中下表区间落在|i,j|中所有元素的和。
     
     由于我们要求的是子数组的和最大值在所有情况中的最小值，可列状态转移方程
                i-1
     f[i][j] =  min{max(f[k][j-1],sub(k+1,i))}
                k=0
     
     对于状态f[i][j],由于我们不能分出空数组，因此合法状态必须有 i>=j。
     对于不合法状态，由于我们的目标是求出最小值，因此可以将那些状态全部初始化为一个很大的数字。
     在上述转移方程中，一旦我们尝试从不合法状态的f[k][j-1]进行转移，那么max后是一个很大的数，不影响外层的min运算。
     
     此外，f[0][0] = 0.
     当 j=1 时，唯一的可能性就是前 i 个数被分成了一段。
     如果枚举的 k=0 ，那么就代表着这种情况；
     如果 k != 0，对应状态f[k][0]是一个不合法的状态，无法进行转移，所以要设f[0][0] = 0
     
     最终答案就是f[n][m]
     */
    
    let initValue = Int(INT32_MAX)
    
    func splitArray(_ nums: [Int], _ m: Int) -> Int {
        
        let n = nums.count
        
        //sub数组中下表为n的数字表示nums中前n个元素的和
        var sub:[Int] = [0]
        for i in 0 ..< n {
            sub.append(sub[i] + nums[i])
        }
        //用例nums = [7,2,5,10,8]；  sub = [0,7,9,14,24,32]
        
        
        var dp = [[Int]](repeating: [Int](repeating: initValue, count: m+1), count: n+1)
        dp[0][0] = 0
        
        for i in 1 ... n{
            for j in 1 ... min(i, m){   //合法必须有i>=j，所以j的枚举上限是min(i, m)
                for k in 0 ..< i {
                    dp[i][j] = min(dp[i][j], max(dp[k][j-1], sub[i]-sub[k]))
                    
                    print("求坐标\(i),\(j)的值，在dp[\(k)][\(j-1)]和sub[\(i)]-sub[\(k)]中取最大值，再和dp[\(i)][\(j)]相比取较小的")
                    print("最终结果为\(dp[i][j])")
                }
            }
        }
    
        return dp[n][m]
    }
    /* nums = [7,2,5,10,8]； m = 2用例下 最终的dp结果为
     
     0      max     max
     
     max    7       max
     
     max    9       max
     
     max    14      7
     
     max    24      24
     
     max    32      18
     
     
     
     */
    
    
    /*
     二分查找+贪心解法
     「使…最大值尽可能小」是二分搜索题目常见的问法。
     
     子数组的最大值范围是 [max(nums) -- sum(nums)]
     设置left = max(nums), right = sum(nums), mid = left + (right-left)/2,
     计算数组和最大值不大于mid对应的子数组个数cnt
     
     如果cnt>m，说明划分的子数组多了，所以mid偏小，left = mid+1
     否则，说明划分的子数组少了，即mid偏大(或者刚好是目标值)，故 right = mid
     
     */
    
    func splitArray2(_ nums: [Int], _ m: Int) -> Int {
        
        var left = 0
        var right = 0
        
        for i in 0 ..< nums.count {
            right = right+nums[i]
            if left < nums[i] {
                left = nums[i]
            }
        }
        
        while left < right {
            let mid = left + (right-left)/2
            if self.check(nums, mid, m) == true{
                right = mid
            }else{
                left = mid + 1
            }
        }
        
        return left
    }
    
    func check(_ nums: [Int], _ mid: Int, _ m: Int) -> Bool{
        var sum = 0
        var cnt = 1
        for i in 0 ..< nums.count{
            if sum + nums[i] > mid {
                cnt += 1
                sum = nums[i]
            }else{
                sum += nums[i]
            }
        }
        return cnt <= m
    }
    
}
